' Written by Craig'n'Dave
Module Module1
    ' Linked list using objects
    Public Class LinkedList

        Private Class Node
            Public data As String
            Public pointer As Node
        End Class

        Private start As Node

        Function add(item As String)
            ' Check memory overflow
            Try
                Dim new_node As New Node
                new_node.data = item
                Dim current_node As Node = start
                ' List is empty
                If IsNothing(current_node) Then
                    new_node.pointer = Nothing
                    start = new_node
                Else
                    ' Item becomes the new start item
                    If item < current_node.data Then
                        start = new_node
                        new_node.pointer = current_node
                    Else
                        ' Find correct position in the list
                        Dim previous_node As node
                        Do While Not IsNothing(current_node) AndAlso current_node.data < item
                            previous_node = current_node
                            current_node = current_node.pointer
                        Loop
                        new_node.pointer = previous_node.pointer
                        previous_node.pointer = new_node
                    End If
                End If
                Return True
            Catch
                Return False
            End Try
        End Function

        Sub delete(item As String)
            Dim new_node As New Node
            Dim current_node As Node = start
            ' Check the list is not empty
            If Not IsNothing(current_node) Then
                ' Item is the start node
                If item = current_node.data Then
                    start = current_node.pointer
                Else
                    ' Find item in the list
                    Dim previous_node As node
                    previous_node = current_node
                    Do While Not IsNothing(current_node) AndAlso item <> current_node.data
                        previous_node = current_node
                        current_node = current_node.pointer
                    Loop
                    If Not IsNothing(current_node) Then
			previous_node.pointer = current_node.pointer
                    End If
                End If
            End If
        End Sub

        Function output()
            Dim items As New List(Of String)
            Dim current_node As node = start
            If Not IsNothing(current_node) Then
                ' Visit each node
                Do While Not IsNothing(current_node)
                    items.Add(current_node.data)
                    current_node = current_node.pointer
                Loop
            End If
            Return items
        End Function
    End Class

    'Main program starts here
    Sub Main()
        Dim items() As String = {"Florida", "Georgia", "Delaware", "Alabama", "California", "Wyoming"}
        Dim linked_list As New LinkedList
        ' Adding items to the linked list
        For index = 0 To items.Length - 1
            linked_list.add(items(index))
        Next
        ' Deleting items from a linked list
        linked_list.delete("Florida")
        ' Output the linked list
        Dim contents = New List(Of String)
        contents = linked_list.output()
        Console.WriteLine(String.Join(", ", contents))
    End Sub

End Module
